#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 022. 括号生成.py
@time: 2022/1/20 10:43
@desc: https://leetcode-cn.com/problems/generate-parentheses/
> 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

@解题思路：
    1. 回溯
    2. t: O(4^n/√n), 卡特兰数，s: O(n)
'''


class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ans = []

        def backtrack(s, left, right):
            if len(s) == 2 * n:
                ans.append(''.join(s))
            if left < n:
                s.append('(')
                backtrack(s, left + 1, right)
                s.pop()
            if left > right:
                s.append(')')
                backtrack(s, left, right + 1)
                s.pop()

        backtrack([], 0, 0)
        return ans
